package com.zwj.interview.单调栈;

import java.util.Stack;

/**
 * 直方图是由排列在同一基线上的相邻柱子组成的图形。输入一个由非负数组成的数组，
 * 数组中的数字是直方图中柱子的高。求直方图中最大矩形面积。假设直方图中柱子的宽都为1。
 * 例如，输入数组[3，2，5，4，6，1，4，2],最大面积是12
 */
public class 直方图最大面积 {

    //单调栈法
    /**
     * 单调栈的基本思想是确保保存在栈中的直方图的柱子的高度是递增排序的。假设从左到右逐一扫描数组中的每根柱子。
     * 如果当前柱子的高度大于位于栈顶的柱子的高度，那么将该柱子的下标入栈；否则，将位于栈顶的柱子的下标出栈，
     * 并且计算以位于栈顶的柱子为顶的最大矩形面积
     * 题解:https://leetcode-cn.com/problems/0ynMMM/solution/jian-zhi-offer-zhuan-xiang-tu-po-ban-shu-jej6/
     */
    public int largestRectangleArea(int[] heights) {
        // 初始化最终结果为0
        int res = 0;
        //栈中存元素下标，栈底到栈顶一次增加
        Stack<Integer> stack = new Stack<>();
        // 将给定的原数组左右各添加一个元素0
        int[] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        //填充新的数组
        for (int i = 1; i < heights.length + 1; i++) {
            newHeights[i] = heights[i - 1];
        }
        // 开始遍历
        for (int i = 0; i < newHeights.length; i++) {
            // 如果栈不为空且当前考察的元素值小于栈顶元素值，
            // 则表示以栈顶元素值为高的矩形面积可以确定
            while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
                // 弹出栈顶元素
                int cur = stack.pop();
                // 获取栈顶元素对应的高
                int curHeight = newHeights[cur];
                // 栈顶元素弹出后，新的栈顶元素就是其左侧边界
                int leftIndex = stack.peek();
                // 右侧边界是当前考察的索引
                int rightIndex = i;
                // 计算矩形宽度
                int curWidth = rightIndex - leftIndex - 1;
                // 计算面积
                res = Math.max(res, curWidth * curHeight);
            }
            // 当前考察索引入栈
            stack.push(i);
        }
        return res;
    }






}
